package com.justnow;

public class Solution2 {
    public int countSubstring(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int ans = 0;

        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                // i为左边索引地址,j为右边索引下标地址
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i +1 ][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }
        return ans;
    }
}
